package com.demo.java.OD251_300.OD291;

import java.util.*;

/**
 * @author bug菌
 * @Source 公众号：猿圈奇妙屋
 * @des： 【查找单入口空闲区域】问题
 * @url： https://blog.csdn.net/weixin_43970743/article/details/146081506
 */
public class OdMain {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        while (scanner.hasNextInt()) {
            // 读取矩阵的行列数
            int numRows = scanner.nextInt();
            int numCols = scanner.nextInt();
            scanner.nextLine();  // 消耗换行符

            // 构建矩阵
            char[][] grid = new char[numRows][numCols];
            for (int i = 0; i < numRows; i++) {
                grid[i] = scanner.nextLine().replaceAll(" ", "").toCharArray();
            }

            // 创建 MaxAreaFinder 对象，查找最大区域
            MaxAreaFinder maxAreaFinder = new MaxAreaFinder(grid);
            int maxArea = maxAreaFinder.findMaxArea();
            String maxEntrance = maxAreaFinder.getMaxEntrance();

            // 输出结果
            printResult(maxArea, maxEntrance);
        }
    }

    // 输出结果
    public static void printResult(int maxArea, String maxEntrance) {
        if (maxArea == 0) {
            System.out.println("NULL");
        } else if (maxEntrance.equals("more")) {
            System.out.println(maxArea);
        } else {
            System.out.println(maxEntrance + " " + maxArea);
        }
    }
}

class MaxAreaFinder {
    private char[][] grid;
    private int numRows;
    private int numCols;
    private int maxArea;
    private String maxEntrance;
    private int[][] directions = {{0, 1}, {0, -1}, {1, 0}, {-1, 0}};

    public MaxAreaFinder(char[][] grid) {
        this.grid = grid;
        this.numRows = grid.length;
        this.numCols = grid[0].length;
        this.maxArea = 0;
        this.maxEntrance = "";
    }

    // 查找最大区域
    public int findMaxArea() {
        for (int i = 0; i < numRows; i++) {
            for (int j = 0; j < numCols; j++) {
                // 如果是边界上的空闲区域'O'
                if (grid[i][j] == 'O' && isOnEdge(i, j)) {
                    int area = calc(copy(grid), i, j, true);
                    if (area > 0) {
                        String entrance = i + " " + j;
                        if (area > maxArea) {
                            maxArea = area;
                            maxEntrance = entrance;
                        } else if (area == maxArea) {
                            maxEntrance = "more";
                        }
                    }
                }
            }
        }
        return maxArea;
    }

    // 获取最大入口
    public String getMaxEntrance() {
        return maxEntrance;
    }

    // 判断是否在边界
    private boolean isOnEdge(int row, int col) {
        return row == 0 || col == 0 || row == numRows - 1 || col == numCols - 1;
    }

    // 深度复制一个矩阵
    private char[][] copy(char[][] src) {
        char[][] copy = new char[src.length][src[0].length];
        for (int i = 0; i < src.length; i++) {
            System.arraycopy(src[i], 0, copy[i], 0, src[0].length);
        }
        return copy;
    }

    // 计算连通区域的大小
    private int calc(char[][] grid, int row, int col, boolean isRuKou) {
        if (!isRuKou && isOnEdge(row, col)) {
            return 0;
        }

        grid[row][col] = 'X';  // 标记已访问
        int area = 1;  // 当前节点计算为区域的一部分

        // 遍历四个方向
        for (int[] direction : directions) {
            int newRow = row + direction[0];
            int newCol = col + direction[1];
            if (newRow >= 0 && newRow < numRows && newCol >= 0 && newCol < numCols && grid[newRow][newCol] == 'O') {
                int subArea = calc(grid, newRow, newCol, false);
                if (subArea == 0) {
                    return 0;
                }
                area += subArea;  // 计算总区域大小
            }
        }

        return area;
    }
}